package com.lw.leetcode.back.b;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * <p>
 * b
 * arr
 * 886. 可能的二分法
 *
 * @author liw
 * @version 1.0
 * @date 2021/7/22 17:23
 */
public class PossibleBipartition {


    public static void main(String[] args) {
        PossibleBipartition test = new PossibleBipartition();

        // true
//        int[][] arr = {{1, 2}, {2, 3}, {3, 4}};
//        int k = 4;

        //true
//        int[][] arr = {{4,7},{4,8},{5,6},{1,6},{3,7},{2,5},{5,8},{1,2},{4,9},{6,10},{8,10},{3,6},{2,10},{9,10},{3,9},{2,3},{1,9},{4,6},{5,7},{3,8},{1,8},{1,7},{2,4}};
//        int k = 10;

        // false
//        int[][] arr = {{1, 2}, {1, 3}, {2, 3}};
//        int k = 3;

        // false
//        int[][] arr = {{1, 2}, {2, 3}, {3, 4}, {4, 5}, {1,5}};
//        int k = 5;

        //
        int[][] arr = {{28, 132}, {6, 167}, {109, 184}, {75, 104}, {81, 93}, {53, 188}, {86, 90}, {57, 185}, {35, 190}, {118, 142}, {19, 143}, {35, 41}, {113, 151}, {35, 121}, {4, 66}, {83, 170}, {94, 167}, {31, 74}, {20, 109}, {80, 133}, {74, 199}, {11, 22}, {40, 104}, {67, 80}, {86, 129}, {39, 70}, {91, 118}, {153, 157}, {72, 192}, {137, 142}, {2, 188}, {76, 155}, {26, 51}, {18, 60}, {93, 116}, {104, 170}, {7, 120}, {23, 183}, {143, 188}, {93, 176}, {73, 113}, {57, 194}, {18, 149}, {13, 127}, {107, 108}, {58, 77}, {26, 89}, {59, 61}, {93, 177}, {31, 200}, {25, 196}, {13, 89}, {19, 122}, {79, 85}, {93, 171}, {4, 87}, {108, 196}, {52, 105}, {44, 58}, {144, 174}, {58, 141}, {41, 179}, {4, 125}, {124, 178}, {23, 126}, {103, 192}, {13, 97}, {24, 59}, {87, 157}, {145, 193}, {91, 198}, {176, 194}, {26, 168}, {80, 85}, {179, 195}, {1, 170}, {19, 183}, {71, 93}, {42, 157}, {25, 92}, {4, 42}, {28, 63}, {50, 108}, {22, 45}, {7, 83}, {72, 193}, {105, 117}, {172, 199}, {142, 184}, {70, 183}, {72, 80}, {123, 188}, {28, 110}, {157, 166}, {5, 167}, {79, 120}, {43, 78}, {7, 186}, {31, 197}, {10, 23}, {35, 125}, {33, 142}, {23, 119}, {167, 196}, {170, 184}, {11, 26}, {118, 199}, {33, 105}, {80, 175}, {104, 188}, {27, 31}, {31, 138}, {19, 53}, {129, 194}, {22, 110}, {3, 22}, {45, 113}, {35, 85}, {88, 142}, {9, 81}, {23, 184}, {49, 113}, {31, 33}, {23, 150}, {5, 59}, {59, 140}, {86, 176}, {18, 48}, {37, 157}, {9, 97}, {29, 96}, {13, 136}, {43, 56}, {93, 114}, {96, 163}, {36, 180}, {26, 52}, {120, 194}, {40, 99}, {26, 186}, {65, 109}, {117, 194}, {7, 103}, {51, 174}, {55, 105}, {47, 188}, {3, 31}, {109, 156}, {158, 170}, {82, 129}, {105, 196}, {87, 108}, {72, 179}, {22, 63}, {28, 134}, {172, 181}, {173, 193}, {55, 170}, {50, 192}, {8, 170}, {32, 167}, {142, 172}, {3, 178}, {36, 44}, {59, 133}, {19, 115}, {23, 187}, {155, 186}, {142, 164}, {35, 135}, {27, 28}, {83, 113}, {78, 199}, {6, 96}, {135, 185}, {165, 185}, {10, 174}, {170, 180}, {2, 25}, {130, 194}, {181, 198}, {10, 192}, {40, 112}, {96, 125}, {65, 152}, {46, 170}, {43, 100}, {8, 194}, {91, 110}, {63, 105}, {141, 174}, {64, 179}, {75, 99}, {103, 185}, {65, 178}, {4, 150}, {19, 150}, {29, 35}, {142, 183}, {35, 64}, {25, 49}, {58, 127}, {7, 66}, {98, 179}, {90, 93}, {103, 109}, {120, 174}, {79, 125}, {117, 170}, {29, 80}, {37, 113}, {4, 127}, {103, 194}, {155, 171}, {19, 72}, {7, 85}, {150, 152}, {35, 143}, {59, 120}, {137, 181}, {96, 141}, {5, 152}, {79, 159}, {110, 193}, {31, 61}, {146, 178}, {25, 34}, {19, 124}, {36, 116}, {28, 57}, {2, 36}, {48, 70}, {20, 23}, {13, 159}, {24, 82}, {23, 42}, {1, 80}, {23, 145}, {26, 195}, {68, 174}, {86, 197}, {26, 72}, {72, 82}, {136, 167}, {68, 178}, {24, 193}, {138, 192}, {49, 80}, {22, 127}, {55, 199}, {26, 114}, {93, 172}, {40, 88}, {4, 102}, {18, 160}, {39, 59}, {31, 110}, {19, 81}, {42, 82}, {139, 170}, {99, 185}, {165, 181}, {17, 108}, {6, 142}, {30, 155}, {59, 87}, {192, 200}, {168, 194}, {36, 115}, {28, 48}, {75, 136}, {13, 111}, {18, 122}, {60, 181}, {28, 46}, {8, 157}, {7, 137}, {76, 105}, {43, 173}, {40, 57}, {85, 174}, {75, 196}, {26, 145}, {9, 148}, {36, 168}, {113, 125}, {67, 170}, {70, 149}, {28, 123}, {33, 96}, {47, 80}, {2, 28}, {35, 118}, {10, 199}, {40, 139}, {96, 120}, {23, 78}, {26, 144}, {56, 174}, {35, 92}, {3, 40}, {78, 142}, {93, 154}, {63, 193}, {152, 169}, {35, 162}, {7, 21}, {28, 190}, {40, 183}, {26, 90}, {32, 185}, {60, 170}, {18, 114}, {73, 86}, {160, 178}, {57, 167}, {148, 157}, {109, 129}, {110, 142}, {111, 179}, {115, 193}, {43, 51}, {105, 135}, {13, 54}, {79, 118}, {3, 96}, {165, 167}, {76, 185}, {103, 199}, {86, 133}, {28, 104}, {25, 154}, {7, 94}, {50, 178}, {155, 200}, {26, 173}, {128, 157}, {28, 135}, {45, 193}, {105, 110}, {4, 47}, {87, 93}, {34, 75}, {70, 74}, {50, 113}, {22, 46}, {70, 116}, {31, 180}, {52, 79}, {9, 134}, {19, 126}, {40, 196}, {7, 163}, {91, 169}, {116, 181}, {22, 122}, {58, 137}, {96, 162}, {82, 166}, {4, 121}, {1, 105}, {139, 181}, {22, 92}, {19, 74}, {35, 100}, {42, 105}, {76, 108}, {76, 142}, {12, 155}, {86, 118}, {110, 199}, {56, 179}, {61, 96}, {52, 167}, {36, 118}, {108, 189}, {7, 11}, {29, 58}, {3, 59}, {27, 86}, {11, 199}, {4, 60}, {52, 86}, {75, 165}, {82, 135}, {18, 62}, {86, 189}, {161, 167}, {99, 199}, {24, 96}, {133, 157}, {13, 139}, {155, 160}, {58, 117}, {28, 126}, {42, 80}, {136, 188}, {109, 133}, {137, 188}, {58, 95}, {35, 115}, {7, 106}, {60, 192}, {71, 86}, {142, 198}, {23, 71}, {36, 140}, {124, 170}, {108, 180}, {75, 126}, {98, 105}, {104, 108}, {136, 193}, {110, 185}, {83, 199}, {32, 43}, {54, 178}, {6, 188}, {25, 117}, {82, 126}, {109, 118}, {28, 95}, {49, 188}, {38, 43}, {33, 36}, {9, 165}, {26, 156}, {45, 155}, {19, 88}, {92, 109}, {67, 178}, {23, 102}, {31, 127}, {43, 77}, {91, 119}, {40, 141}, {23, 92}, {34, 91}, {45, 79}, {59, 102}, {22, 51}, {18, 115}, {59, 182}, {86, 92}, {5, 188}, {25, 121}, {13, 64}, {13, 120}, {61, 70}, {58, 184}, {81, 105}, {54, 86}, {92, 157}, {35, 138}, {72, 188}, {4, 177}, {9, 10}, {75, 90}, {74, 193}, {129, 167}, {35, 144}, {96, 190}, {94, 193}, {94, 185}, {127, 170}, {82, 173}, {60, 113}, {97, 108}, {21, 91}, {31, 100}, {32, 109}, {83, 91}, {89, 108}, {40, 116}, {50, 179}, {92, 108}, {28, 153}, {128, 181}, {75, 158}, {35, 173}, {78, 185}, {6, 170}, {32, 178}, {132, 155}, {25, 71}, {40, 41}, {83, 185}, {17, 25}, {7, 42}, {106, 192}, {93, 165}, {22, 120}, {17, 170}, {41, 181}, {37, 167}, {40, 85}, {177, 193}, {13, 144}, {23, 116}, {120, 152}, {77, 179}, {90, 109}, {7, 200}, {82, 92}, {31, 139}, {43, 81}, {28, 184}, {9, 72}, {10, 70}, {57, 70}, {75, 138}, {21, 40}, {40, 56}, {43, 119}, {23, 29}, {167, 176}, {105, 127}, {27, 40}, {31, 168}, {93, 132}, {31, 191}, {146, 193}, {34, 58}, {17, 18}, {166, 192}, {78, 170}, {28, 139}, {158, 188}, {78, 105}, {123, 178}, {70, 102}, {9, 151}, {151, 174}, {26, 126}, {77, 82}, {59, 101}, {53, 70}, {13, 137}, {154, 178}, {29, 91}, {21, 109}, {149, 152}, {28, 120}, {61, 157}, {53, 96}, {23, 107}, {105, 163}, {152, 154}, {35, 117}, {3, 28}, {31, 145}, {31, 158}, {93, 122}, {18, 129}, {7, 132}, {59, 65}, {173, 194}, {75, 107}, {82, 98}, {128, 185}, {9, 182}, {31, 47}, {26, 172}, {51, 194}, {31, 45}, {175, 199}, {54, 93}, {44, 170}, {120, 192}, {67, 174}, {100, 192}, {39, 181}, {13, 130}, {137, 193}, {52, 58}, {7, 71}, {51, 142}, {80, 156}, {145, 181}, {22, 55}, {127, 181}, {89, 105}, {57, 80}, {44, 109}, {91, 111}, {88, 155}, {19, 177}, {40, 149}, {23, 52}, {166, 185}, {36, 76}, {32, 36}, {37, 193}, {9, 38}, {69, 157}, {84, 155}, {79, 177}, {41, 58}, {83, 178}, {23, 165}, {49, 70}, {18, 172}, {88, 167}, {69, 167}, {73, 188}, {22, 144}, {52, 192}, {96, 176}, {22, 103}, {25, 60}, {55, 70}, {70, 154}, {10, 105}, {80, 186}, {76, 181}, {168, 174}, {19, 73}, {35, 150}, {83, 93}, {9, 99}, {126, 157}, {71, 185}, {75, 186}, {34, 80}, {59, 95}, {137, 152}, {2, 174}, {23, 177}, {152, 180}, {66, 199}, {22, 34}, {11, 75}, {43, 159}, {11, 194}, {82, 110}, {36, 81}, {57, 58}, {67, 75}, {121, 192}, {40, 200}, {40, 49}, {7, 39}, {108, 118}, {86, 190}, {11, 23}, {4, 101}, {155, 175}, {17, 75}, {53, 194}, {86, 144}, {34, 36}, {108, 173}, {112, 192}, {40, 125}, {9, 100}, {60, 96}, {93, 146}, {95, 181}, {68, 188}, {30, 80}, {5, 7}, {68, 105}, {72, 194}, {28, 55}, {35, 84}, {5, 19}, {173, 199}, {75, 116}, {36, 88}, {80, 121}, {52, 82}, {35, 186}, {48, 82}, {122, 185}, {132, 170}, {38, 82}, {97, 185}, {24, 199}, {179, 189}, {157, 190}, {18, 184}, {28, 92}, {58, 156}, {77, 80}, {74, 82}, {184, 185}, {40, 94}, {2, 108}, {139, 174}, {36, 50}, {117, 167}, {77, 170}, {183, 185}, {145, 178}, {59, 119}, {13, 24}, {32, 86}, {108, 121}, {18, 90}, {134, 178}, {25, 87}, {5, 28}, {9, 89}, {74, 105}, {23, 57}, {105, 169}, {31, 166}, {44, 142}, {141, 142}, {2, 91}, {171, 194}, {108, 160}, {102, 192}, {142, 173}, {35, 187}, {52, 181}, {131, 188}, {31, 55}, {122, 170}, {26, 71}, {74, 93}, {142, 182}, {74, 194}, {113, 154}, {86, 162}, {80, 158}, {4, 154}, {57, 108}, {22, 68}, {28, 111}, {7, 95}, {37, 155}, {59, 98}, {42, 93}, {53, 152}, {75, 135}, {26, 53}, {105, 147}, {45, 194}, {159, 199}, {143, 185}, {9, 66}, {69, 113}, {128, 178}, {58, 63}, {37, 79}, {81, 109}, {116, 142}, {161, 181}, {53, 86}, {9, 150}, {35, 148}, {86, 165}, {28, 72}, {84, 193}, {76, 82}, {7, 190}, {22, 198}, {155, 168}, {71, 157}, {126, 152}, {25, 145}, {80, 171}, {43, 121}, {59, 123}, {26, 183}, {55, 157}, {138, 179}, {33, 79}, {28, 149}, {59, 81}, {79, 146}, {39, 113}, {149, 170}, {107, 109}, {22, 32}, {6, 174}, {34, 155}, {4, 99}, {25, 134}, {35, 62}, {142, 161}, {108, 112}, {59, 136}, {96, 116}, {19, 106}, {58, 147}, {37, 188}, {24, 31}, {40, 89}, {78, 155}, {146, 152}, {15, 23}, {105, 148}, {28, 125}, {17, 192}, {26, 83}, {82, 186}, {50, 167}, {35, 66}, {22, 72}, {43, 85}, {31, 132}, {7, 107}, {147, 194}, {80, 184}, {76, 199}, {103, 174}, {36, 124}, {152, 189}, {108, 187}, {28, 138}, {19, 173}, {109, 186}, {74, 108}, {123, 179}, {36, 90}, {14, 170}, {18, 156}, {87, 193}, {70, 123}, {41, 152}, {165, 194}, {12, 35}, {162, 188}, {35, 130}, {49, 155}, {28, 94}, {151, 170}, {17, 167}, {178, 196}, {23, 137}, {8, 105}, {86, 169}, {28, 116}, {26, 100}, {119, 193}, {80, 153}, {88, 96}, {152, 158}, {108, 148}, {108, 153}, {25, 51}, {26, 163}, {36, 123}, {84, 93}, {58, 200}, {5, 26}, {47, 167}, {59, 69}, {89, 170}, {64, 108}, {4, 33}, {7, 20}, {40, 137}, {36, 164}, {1, 91}, {19, 120}, {27, 113}, {42, 59}, {16, 58}, {3, 93}, {117, 174}, {82, 172}, {56, 199}, {23, 124}, {31, 101}, {35, 126}, {32, 108}, {18, 83}, {52, 179}, {31, 131}, {19, 42}, {44, 105}, {14, 86}, {108, 125}, {25, 94}, {104, 194}, {82, 89}, {22, 150}, {37, 70}, {105, 175}, {22, 47}, {28, 182}, {27, 80}, {25, 64}, {22, 136}, {19, 21}, {122, 179}, {18, 33}, {94, 181}, {105, 143}, {33, 113}, {28, 195}, {70, 158}, {147, 157}, {13, 119}, {134, 152}, {7, 53}, {4, 184}, {108, 138}, {59, 125}, {13, 191}, {28, 30}, {85, 91}, {51, 199}, {11, 105}, {55, 181}, {108, 190}, {25, 69}, {19, 160}, {30, 185}, {119, 152}, {43, 147}, {113, 132}, {53, 179}, {10, 40}, {62, 194}, {88, 178}, {165, 199}, {111, 192}, {136, 170}, {108, 119}, {109, 158}, {131, 178}, {72, 178}, {15, 179}, {105, 154}, {28, 127}, {140, 174}, {33, 108}, {19, 180}, {109, 123}, {28, 175}, {107, 192}, {180, 199}, {19, 195}, {154, 199}, {56, 170}, {80, 103}};
        int k = 200;

        boolean b = test.possibleBipartition(k, arr);
        System.out.println(b);
    }

    private int[] flags;
    private Map<Integer, List<Integer>> map;

    public boolean possibleBipartition(int n, int[][] dislikes) {
        if (dislikes.length == 0) {
            return true;
        }

        this.flags = new int[n + 1];
        Map<Integer, List<Integer>> map = new HashMap<>(n << 1);
        for (int[] dislike : dislikes) {
            List<Integer> list = map.computeIfAbsent(dislike[0], v -> new ArrayList<>());
            list.add(dislike[1]);
            list = map.computeIfAbsent(dislike[1], v -> new ArrayList<>());
            list.add(dislike[0]);
            flags[dislike[0]] = 1;
            flags[dislike[1]] = 1;

        }
        boolean[] a = new boolean[n + 1];
        boolean[] b = new boolean[n + 1];
        this.map = map;

        for (int i = 0; i <= n; i++) {
            if (flags[n] == 1) {
                a[n] = true;
                if (!find(n, a, b)) {
                    return false;
                }
            }
        }
        return true;
    }

    private boolean find(int index, boolean[] a, boolean[] b) {
        List<Integer> list = map.get(index);
        if (list == null) {
            return true;
        }
        for (int value : list) {
            if (a[value]) {
                return false;
            }
            if (b[value]) {
                continue;
            }
            b[value] = true;
            if (!find(value, b, a)) {
                return false;
            }
        }
        return true;
    }

}
